package cover.alg;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.VertexCovers;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

import cover.vertex.Vertex;
/**
 * usefull utils
 *
 */
public class Utils {
	/**
	 * check if the cover is covering graph
	 * 
	 * @param cover
	 * @param graph
	 * @return
	 */
	private static boolean check(Set<Vertex> cover,Graph<Vertex, DefaultEdge> graph) {
		for (DefaultEdge edge : graph.edgeSet()) {
			if(!cover.contains(graph.getEdgeSource(edge))){
				if(!cover.contains(graph.getEdgeTarget(edge)))
					return false;
			}
		}
		return true;
	}
	/**
	 * remove some useless vertex
	 * local optimisation technic,greedy
	 * @param cover
	 * @param graph
	 * @return
	 */
	public static Set<Vertex> lot(Set<Vertex> cover,Graph<Vertex, DefaultEdge> graph){
		for(Vertex tempVertex : cover){
			Set<Vertex> proposition = copyOfVertex(cover);
			proposition.remove(tempVertex);
			if(check(proposition,graph))
				return lot(proposition,graph);
		}
		return cover;
	}
	
	//simply addition one more element to cover
	public static Set<Vertex> mutationOneToCover(Set<Vertex> cover,Graph<Vertex, DefaultEdge> graph){
		for(Vertex tempVertex : cover){
			Set<Vertex> proposition = copyOfVertex(cover);
			proposition.remove(tempVertex);
			if(check(proposition,graph))
				return proposition;
			else {
				for(Vertex vertex : cover){
					if(!vertex.equals(tempVertex) && !proposition.contains(vertex)){
						proposition.add(vertex);
						if(check(proposition,graph))
							return proposition;
					}
				}
			}
		}
		for(Vertex tempVertex : graph.vertexSet()){
			if(!cover.contains(tempVertex)){
				cover.add(tempVertex);
				return cover;
			}
		}
		return cover;
	}
	//deleting a half of cover and greedy adding another one
	public static Set<Vertex> mutationHalfToCover(Set<Vertex> cover,Graph<Vertex, DefaultEdge> graph){
		Iterator<Vertex> iter = cover.iterator();
		Set<Vertex> proposition = new HashSet<Vertex>();
		for(int i = 0;i<cover.size()/2;i++){
			proposition.add(iter.next());
		}
		if (check(proposition,graph))
			return proposition;
		for(Vertex tempVertex : graph.vertexSet()){
			if(!proposition.contains(tempVertex)){
				proposition.add(tempVertex);
				if (check(proposition,graph))
					return proposition;
			}
		}
		return cover;
	}
	//choosing one vertex out of cover and greedy algorithm to it
	//with container(not using vertex)
	public static Set<Vertex> mutationOneAnotherGreedy(Set<Vertex> cover,Set<Vertex> container,Graph<Vertex, DefaultEdge> graph){
		for(Vertex vertex : container){
			for(Vertex tempVertex : Graphs.neighborListOf(graph,vertex)){
				graph.removeAllEdges(vertex,tempVertex);
			}
			Set<Vertex> newCover = VertexCovers.findGreedyCover((UndirectedGraph<Vertex,DefaultEdge>)graph);
			newCover.add(vertex);
			return newCover;
		}
		return cover;
	}
	//choosing one vertex out of cover and greedy algorithm to it
	public static Set<Vertex> mutationOneAnotherGreedy(Set<Vertex> cover,Graph<Vertex, DefaultEdge> graph){
		for(Vertex vertex : graph.vertexSet()){
			if(!cover.contains(vertex)){
				for(Vertex tempVertex : Graphs.neighborListOf(graph,vertex)){
					graph.removeAllEdges(vertex,tempVertex);
				}
				Set<Vertex> newCover = VertexCovers.findGreedyCover((UndirectedGraph<Vertex,DefaultEdge>)graph);
				newCover.add(vertex);
				return newCover;
			}
		}
		return cover;
	}
	//combination of mutations
	public static Set<Vertex> mutationCombi(Set<Vertex> cover,Set<Vertex> container,Graph<Vertex, DefaultEdge> graph){
		if (container.isEmpty())
			return mutationHalfGreedy(cover,graph);
		else 
			return mutationOneAnotherGreedy(cover,container,graph);
	}
	//deleting a half of cover and greedy adding another one
	public static Set<Vertex> mutationHalfGreedy(Set<Vertex> cover,Graph<Vertex, DefaultEdge> graph){
		Iterator iter = cover.iterator();
		Set<Vertex> proposition = new HashSet<Vertex>();
		for(int i = 0;i<cover.size()/2;i++){
			Vertex tempVertex = (Vertex)iter.next();
			proposition.add(tempVertex);
			for(Vertex vertex : Graphs.neighborListOf(graph,tempVertex)){
				graph.removeAllEdges(vertex,tempVertex);
			}
		}
		if (check(proposition,graph))
			return proposition;
		proposition.addAll(VertexCovers.findGreedyCover((UndirectedGraph<Vertex,DefaultEdge>)graph));
		return proposition;
	}
		
	/**
	 * the whole graph + some subgraph without one vertex
	 * 
	 * @param graph
	 * @return
	 */
	public static LinkedList<Set<Vertex>> getFirstPopulation(LinkedList<Vertex> vertexList){
		LinkedList<Set<Vertex>> firstPopulation = new LinkedList<Set<Vertex>>();
		Set<Vertex> cover = new HashSet<Vertex>();
		cover.addAll(vertexList);
		firstPopulation.add(cover);
		for(int i = 0;i<vertexList.size();i++){
			List<Vertex> temp = new LinkedList<Vertex>();
			if(i>0)
				temp.addAll(vertexList.subList(0,i-1));
			if(i<vertexList.size()-1)
				temp.addAll(vertexList.subList(i+1,vertexList.size()));
			cover = new HashSet<Vertex>();
			cover.addAll(temp);
			firstPopulation.add(cover);
		}
		return firstPopulation;
	}
	
	public static LinkedList<Set<Vertex>> getFirstPopulation(Graph<Vertex, DefaultEdge> graph){
		LinkedList<Set<Vertex>> firstPopulation = new LinkedList<Set<Vertex>>();
		Set<Vertex> allVertex = graph.vertexSet();
		firstPopulation.add(allVertex);
		for(Vertex vertex : allVertex){
			Set<Vertex> temp = copyOfVertex(allVertex);
			temp.remove(vertex);
			if(check(temp,graph))
				firstPopulation.addFirst(temp);
		}
		return firstPopulation;
	}
	
	public static Set<Vertex> copyOfVertex(Set<Vertex> set){
		Set<Vertex> clone = new HashSet<Vertex>();
		for(Vertex tempVertex : set){
			try {
				clone.add(tempVertex.getCopy());
			} catch (CloneNotSupportedException e) {
				e.printStackTrace();
			}
		}
		return clone;
	}
	
	public static Graph<Vertex, DefaultEdge> copyOfGraph(Graph<Vertex, DefaultEdge> graph){
		Graph<Vertex, DefaultEdge> clone = new SimpleGraph<Vertex, DefaultEdge>(
				DefaultEdge.class);
		for (Vertex vertex : graph.vertexSet()){
			try {
				clone.addVertex(vertex.getCopy());
			} catch (CloneNotSupportedException e) {
				e.printStackTrace();
			}
		}
		for (DefaultEdge edge : graph.edgeSet()){
			clone.addEdge(graph.getEdgeSource(edge),graph.getEdgeTarget(edge));
		}
		return clone;
	}
	
	public static Set<DefaultEdge> copyOfEdges(Set<DefaultEdge> edges){
		Set<DefaultEdge> clone = new HashSet<DefaultEdge>();
		for (DefaultEdge edge : edges){
			clone.add((DefaultEdge) edge.clone());
		}
		return clone;
	}
}
